МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" Інститут КНІТ Кафедра ПЗ ЗВІТ До лабораторної роботи № 4 На тему: “Послідовний метод компонування за зв’язністю” З дисципліни: “Комбінаторні методи та алгоритми” Лектор: проф. кафедри ПЗ Базилевич Р.П. Львів – 2013 Тема роботи: Послідовний метод компонування за зв’язністю Мета роботи: Дослідження алгоритму послідовного методу компонування за зв’язністю. Теоретичні відомості Завданням даної лабораторної роботи є процес розбиття елементів графу на вузли за допомогою ілюстративної програми та тестування конкретних випадків з її допомогою. Як приклад, для порівняльної характеристики використати стандартну тестову задачу Штейнберга, а також графи з різною кількістю елементів для дослідження характеристик методу. В ході дослідження процесу розбиття на вузли елементів графу зробити висновки відносно обчислювальної складності та точності методу. Розглянемо загальну схему методу й особливості його конкретної реалізації на ЕОМ. Нехай задана схема множина елементів E={e1, ... , en} і матриця суміжності, яка описує зв’язки між цими елементами. Визначемо послідовний процес призначення елементів ei
E (i=1, ..., n) у вузли Tr(r=1, 2, ...,
), на кожному кроці якого вибирається один із нерозподілених елементів і приписується черговому вузлу. Вузол вважається завершеним, якщо число елементів у вузлі дорівнює заданому числу k або призначення любого з нерозподілених елементів призводить до утворення такого числа зовнішніх зв'язків вузла, що перевищує гранично припустиме значення v. Після завершення чергового вузла аналогічна процедура повторюється для наступного вузла, причому кандидатами для призначення є елементи, не включені в попередні вузли. Процес закінчується, коли всі елементи з множини Е розподілені. Зауважимо, що елемент е0, що відповідає набору зовнішніх виводів схеми, рахується розподіленим у вузол T0. Тактика призначення елементів складається в наступному. n°1. На черговому кроці процесу виділяються ті з ще нерозподілених елементів, включення кожного з яких у даний вузол не порушує обмежень по числу елементів і виводів вузла. n°2. Елементом, який включений у вузол на черговому кроці, є той із вибраних у n°1 елементів, що має найбільше число зв'язків з елементами, уже поміщеними у вузол (максимальна кон’юнкція). При кількох таких елементах включається той з них, що має мінімальну диз'юнкцію з елементами вузла. Код програми namespace poslid { public partial class Form1 : Form { public struct pointS { public int x; public int y; public int color; public bool used; } pointS[] points = new pointS[1]; private void numericUpDown1_ValueChanged(object sender, EventArgs e) { int val = (int)numericUpDown1.Value; dataGridView1.Columns.Clear(); for (int i = 0; i < val; i++) { //col dataGridView1.Columns.Add('x' + (i + 1).ToString(), 'x' + (i + 1).ToString()); dataGridView1.Columns[dataGridView1.Columns.Count - 1].Width = 25; //row dataGridView1.Rows.Add(1); dataGridView1.Rows[dataGridView1.Rows.Count - 1].HeaderCell.Value = 'x' + (i + 1).ToString(); dataGridView1.RowHeadersWidth = 50; } Random r = new Random(); for (int i = 0; i < dataGridView1.Rows.Count; i++) for (int j = 0; j < dataGridView1.Columns.Count; j++) { double n =r.NextDouble() * 10 - r.NextDouble() * 10; if (n < 0) n = 0; if (i == j) n = 0; if (i > j) n = Double.Parse(dataGridView1.Rows[j].Cells[i].Value.ToString()); dataGridView1.Rows[i].Cells[j].Value = (int)(n); } points = n...